package com.wcj.linktable;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *    a1  a2
 *            c1  c2  c3
 *b1  b2  b3
 */
public class 相交链表 {


    /**
     * 每步操作需要同时更新指针 \textit{pA}pA 和 \textit{pB}pB。
     *
     * 如果指针 \textit{pA}pA 不为空，则将指针 \textit{pA}pA 移到下一个节点；
     * 如果指针 \textit{pB}pB 不为空，则将指针 \textit{pB}pB 移到下一个节点。
     *
     * 如果指针 \textit{pA}pA 为空，则将指针 \textit{pA}pA 移到链表 \textit{headB}headB 的头节点；
     * 如果指针 \textit{pB}pB 为空，则将指针 \textit{pB}pB 移到链表 \textit{headA}headA 的头节点。
     *
     * 当指针 \textit{pA}pA 和 \textit{pB}pB 指向同一个节点或者都为空时，返回它们指向的节点或者 \text{null}null。
     * a1 a2 c1 c2 c3 b1 b2 b3 c1 c2 c3
     * b1 b2 b3 c1 c2 c3 a1 a2 c1 c2 c3
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode pointA = headA;
        ListNode pointB = headB;
        while (pointA != pointB){
            if (pointA != null){
                pointA = pointA.next;
            }else {
                pointA = headB;
            }
            if (pointB != null){
                pointB = pointB.next;
            }else {
                pointB = headA;
            }
        }
        return pointA;
    }
}
